#ifndef RESOLVETABLET_H_
#define RESOLVETABLET_H_

#include <iostream>
#include <assert.h>
#include <ext/hash_map>
namespace stdext
{
	using namespace __gnu_cxx;
}

#include "graph_support/GraphSupport.h"

namespace GRAPH_SUPPORT_NS
{
namespace utils
{

/**
 * interface:
 * 		map : KeyT -> ValT
 * implementations:
 * 		stdext::hash_map in general case
 * and
 * 		std::vector< ValT > in case of KeyT = int
 *
 * see usage in VectorGraph for details
 */

template<
	typename KeyT,
	typename ValT,
	typename HashFn = stdext::hash< KeyT >,
	typename CmpFn = stdext::equal_to< KeyT >
	>
class ResolveTableHash
{
public:
	typedef typename stdext::hash_map< KeyT, ValT, HashFn, CmpFn > Table;
public:
	template< typename IterT >
	static void init( Table & table, IterT beg, IterT end )
	{
	}
	static bool hasKey( const Table & table, const KeyT & key )
	{
		return table.find( key ) != table.end();
	}
	static const ValT & get( const Table & table, KeyT key, const ValT & defaultValue )
	{
		typename Table::const_iterator fiter = table.find( key );
		if ( fiter == table.end() )
		{
			return defaultValue;
		} else
		{
			const ValT & result = fiter->second;
			return result;
		}
	}
};

template<
	typename KeyT,
	typename ValT,
	typename HashFn = stdext::hash< KeyT >,
	typename CmpFn = stdext::equal_to< KeyT >
	>
class ResolveTableType : ResolveTableHash< KeyT, ValT, HashFn, CmpFn >
{
private:
	typedef ResolveTableHash< KeyT, ValT, HashFn, CmpFn > Super;
public:
	typedef typename Super::Table Table;
public:
	template< typename IterT >
	static void init( Table & table, IterT beg, IterT end )
	{
		Super::init( table, beg, end );
	}
	static bool hasKey( const Table & table, const KeyT & key )
	{
		return Super::hasKey( table, key );
	}
	static const ValT & get( const Table & table, KeyT key, const ValT & defaultValue )
	{
		return Super::get( table, key, defaultValue );
	}
};

template< typename ValT, typename HashFn, typename CmpFn >
class ResolveTableType< int, ValT, HashFn, CmpFn >
{
private:
	class SHVec : public std::vector< ValT >
	{
	public:
		SHVec()
			: shift( 0 )
		{
		}
		ValT & operator [] ( int p )
		{
			p += shift;
			assert( p >= 0 );
			return std::vector< ValT >::operator[] ( p );
		}
		const ValT & operator [] ( int p ) const
		{
			p += shift;
			assert( p >= 0 );
			return std::vector< ValT >::operator[] ( p );
		}
		void init( int min, int max )
		{
			shift = -min;
			int sz = max - min + 1;
			assert( sz >= 0 );
			std::vector< ValT >::resize( sz );
		}
		bool hasKey( int key ) const
		{
			int upBound = -shift + std::vector< ValT >::size();
			return key >= -shift && key < upBound;
		}
	private:
		int shift;
	};
public:
	typedef SHVec Table;
public:
	template< typename IterT >
	static void init( Table & table, IterT beg, IterT end )
	{
		int max = beg == end ? -1 : - ( 1 << 30 );
		int min = 0;
		for ( std::vector< int >::const_iterator it = beg; it != end; ++it )
		{
			max = std::max( max, *it );
			min = std::min( min, *it );
		}
		table.init( min, max );
	}
	static bool hasKey( const Table & table, int key )
	{
		return table.hasKey( key );
	}
	static const ValT & get( const Table & table, int key, const ValT & defaultValue )
	{
		if ( !hasKey( table, key ) )
		{
			return defaultValue;
		} else
		{
			return table[key];
		}
	}
};

}
}

#endif /* RESOLVETABLET_H_ */
